package com.gitee.ywj1352.算法.week02;

import java.util.ArrayList;
import java.util.List;

/**
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 */
public class 括号生成 {

    /**
     * 输入：n = 3
     * 输出：["((()))","(()())","(())()","()(())","()()()"]
     *
     * @param n
     * @return
     */
    public static List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        char[] arr = new char[2 * n];
        generate(0, 2 * n, 0, arr, res);
        return res;
    }


    public static void generate(int n, int max, int count, char[] res, List<String> resList) {
        //1.跳出 条件
        if (n >= max || count < 0) {
            if (count == 0 && n == max) {
                resList.add(new String(res));
            }
            return;
        }
        // 2. 递归过程
        res[n] = '(';
        generate(n + 1, max, count + 1, res, resList);
        res[n] = ')';
        generate(n + 1, max, count - 1, res, resList);
    }

    public static ArrayList<String> generateParenthesis2(int n) {
        // write code here
        ArrayList<String> res = new ArrayList<String>();
        helper(n * 2, 0, 0, "", res);
        return res;
    }


    private static void helper(int n, int level, int point, String str, List<String> res) {
        if (n == level || point < 0) {
            if (point == 0) {
                res.add(str);
            }
            return;
        }
        helper(n, level + 1, point + 1, str + "(", res);
        helper(n, level + 1, point - 1, str + ")", res);
    }

    public static void main(String[] args) {

        List<String> strings = generateParenthesis2(5);

        System.out.println(strings);

    }
}
